//==============================================================================
// Copyright (c) 2008-2013 Niall Ryan. All Rights Reserved.
//==============================================================================

#ifndef HYDRA_STACKS_LOCKFREESTAMPEDSTACK_H
#define HYDRA_STACKS_LOCKFREESTAMPEDSTACK_H 1

#include "hydra/allocators/BasicAllocator.h"
#include "hydra/backoff/Backoff.h"

namespace Hydra
{
	/**
	* Lock-free stack, uses stamped references to avoid the ABA problem.
	*/
	template<typename T, typename Allocator=BasicAllocator>
	class LockFreeStampedStack
	{
	public:
		LockFreeStampedStack();
		~LockFreeStampedStack();

		void push(const T& value);
		bool pop(T* value);

	private:
		struct Node
		{
			T m_value;
			Node* m_next;
		};
		Allocator m_alloc;
		AtomicPair<Node*, unsigned int> m_top;
	};

	//==================================================================================================
	//==================================================================================================
	//==================================================================================================

	template<typename T, typename Allocator>
	inline LockFreeStampedStack<T, Allocator>::LockFreeStampedStack()
	{
		m_top.set(NULL, 0);
	}

	template<typename T, typename Allocator>
	inline LockFreeStampedStack<T, Allocator>::~LockFreeStampedStack()
	{
		Node* node = m_top.getFirst();
		while( node )
		{
			Node* next = node->m_next;
			m_alloc.destroy(node);
			node = next;
		}
	}

	template<typename T, typename Allocator>
	inline void LockFreeStampedStack<T, Allocator>::push(const T& value)
	{
		Node* newNode = m_alloc.create<Node>();
		newNode->m_value = value;
		Backoff backoff;
		while( true )
		{
			Node* oldTop;
			unsigned int oldStamp;
			m_top.get(&oldTop, &oldStamp);
			newNode->m_next = oldTop;
			if( m_top.compareAndSwap(newNode, oldStamp+1, oldTop, oldStamp) )
				break;
			else
				backoff.wait();
		}
	}

	template<typename T, typename Allocator>
	inline bool LockFreeStampedStack<T, Allocator>::pop(T* value)
	{
		Backoff backoff;
		while( true )
		{
			Node* oldTop;
			unsigned int oldStamp;
			m_top.get(&oldTop, &oldStamp);
			if( !oldTop )
				return false;
			Node* newTop = oldTop->m_next;
			if( m_top.compareAndSwap(newTop, oldStamp+1, oldTop, oldStamp) )
			{
				*value = oldTop->m_value;
				m_alloc.destroy(oldTop);
				return true;
			}
			backoff.wait();
		}
	}
}

#endif
